package com.tgy.greedy;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @Author: tgy
 * @Date: 2020-11-04 13:39
 *
 * 假设有 25 分、10 分、5 分、1 分的硬币，现要找给客户 41 分的零钱，如何办到硬币个数最少?
 *
 */
public class MoneyChange {

    private Integer[] moneys = {1,5,20,25};

    public int change(int money) {

        Arrays.sort(moneys, Comparator.reverseOrder());

        int index = 0,count = 0;

        while (index < moneys.length) {


            if (money < moneys[index]) {

                index++;
                continue;
            }

            System.out.println(moneys[index]);
            money -= moneys[index];
            count++;
        }

        return count;
    }

}
